一个非典型的网络流问题

2017-04-16 15:30:54 By _Itachi

有 $n$ 个任务，两台机器。任务 $i$ 在第一台机器上执行的花费为 $A_i$ ，在第二台机器上执行的花费为$B_i$ 。有 $M$ 个关系 $(a_k,b_k)$，如果 $a_k$ , $b_k$ 两个任务在相同机器上执行会产生额外的代价 $w_k$ 。问，如何分配这n个任务使得总花费最少。

这是在51nod上看到的一个问题，当时发现这个不可以拆二分图所以无法反转源汇，然后在51nod上这个问题莫名其妙有了个答案然后结束了，答案是彭天翼的论文《浅析一类最小割问题》，但是上面的内容也没有解决这个问题，所以提这个问希望UOJ的dalao们救救萌新！

r_64

poj3469 网上好像有不少题解。。

2017-04-16 18:40:06
回复

613

我感觉这个问题大概能和一般图全局最大割互相规约，然后有一个结论是一般图全局最大割能规约到3sat，我来想想细节上对不对

2017-04-16 21:10:06
回复

_Itachi

回复 @ztr：那么假如S为1，T为3，S到2之间边容量为200，2到T之间边容量为300，那么S到T的最大割是300还是500？最感觉这玩意怪怪的。。

2017-04-17 17:50:06
回复

riteme

感觉有道理@613，因为条件(a,b)可以变为a和b之间有边相连，收益是w，这样就变成解决一般图最大割问题了。如果原问题可以解决，那么任意一般图的最大割都可以解决。据我所知，一般图最大割好像是不可做的......

2017-04-18 08:38:35
回复

EtaoinWu

一般图最大割是个NP-Hard。证明：3-sat规约到nae 4sat规约到nae 3sat规约到最大割 nae sat是指每个句子都是NAE(x1, not x2, ...)的形式，nae表示不全相等最后一步的规约过程如下对于每个nae3sat变量建立两个点xi, not xi 假设一共有n个变量 m个句子 xi与not xi之间连权值M的边 M=10*m 对于每个句子nae(a,b,c)连a-b, b-c, a-c这三条无向边，权值为1 查询是否有>=n*M+2m的割参考文献http://www.cs.cornell.edu/courses/cs4820/2014sp/notes/reduction-maxcut.pdf

2017-04-19 15:10:34
回复

BillXu2000

所以说这是不是有点标题党？

2017-04-21 19:20:05
回复

matthew99

非典都十多年了，怎么现在还有。

2017-04-22 12:02:29
回复

发表评论

可以用@mike来提到mike这个用户，mike会被高亮显示。如果你真的想打“@”这个字符，请用“@@”。

_Itachi的博客

博客

一个非典型的网络流问题

评论

发表评论